package leetcode.editor.cn.q1_300.q100;

/**
 * 115 的递归版本 果然超时了
 *
 * @author qidi
 * @date 2022-01-07 10:23:31
 */
class Q0115_DistinctSubsequences_bak {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        StringBuilder cur = null;
        int num;

        public int numDistinct(String s, String t) {
            if (s.length() < t.length()) return 0;

            cur = new StringBuilder();
            num = 0;
            process(s, t, 0);
            return num;
        }

        private void process(String s, String t, int i) {
            if (cur.length() > t.length()) return;

            if (cur.length() == t.length()) {
                if (cur.toString().equals(t)) num++;
                return;
            }

            if (i >= s.length()) return;

            cur.append(s.charAt(i));
            process(s, t, i + 1);
            cur.deleteCharAt(cur.length() - 1);
            process(s, t, i + 1);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0115_DistinctSubsequences_bak().new Solution();
        System.out.println(solution.numDistinct("rabbbit", "rabbit"));
        System.out.println(solution.numDistinct("babgbag", "bag"));
    }
}